//二叉搜索树

class Node {
    constructor(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
}

class LxBinarySearchTree {
    constructor() {
        this.root = null;
    }

    insertNode(node, newNode) {
        if (node.key > newNode.key) {
            if (node.left) {
                this.insertNode(node.left, newNode);
            } else {
                node.left = newNode;
            }
        } else {
            if (node.right) {
                this.insertNode(node.right, newNode);
            } else {
                node.right = newNode;
            }
        }
    }

    insert(key) {
        const newNode = new Node(key);
        if (this.root) {
            this.insertNode(this.root, newNode);
        } else {
            this.root = newNode;
        }
    }

    preOrderTraversal(handler) {
        this.preOrderTraversalNode(this.root, handler);
    }

    preOrderTraversalNode(node, handler) {
        if (node != null) {
            // 递归
            handler(node.key);
            this.preOrderTraversalNode(node.left, handler);
            this.preOrderTraversalNode(node.right, handler);
        }
    }

    getMin() {
        let current = this.root;
        while (current.left) {
            current = current.left;
        }
        return current.key;
    }

    getMax() {
        let current = this.root;
        console;
        while (current.right) {
            current = current.right;
        }
        return current.key;
    }

    search(key) {
        let current = this.root;
        if (current) {
            while (current && key !== current.key) {
                if (key > current.key) {
                    current = current.right;
                } else {
                    current = current.left;
                }
            }
            if (current) {
                return current;
            }
        }
        return false;
    }

    delete(key) {
        let current = this.root;
        let parent = null;
        let isLeftChild = true;
        while (current && key !== current.key) {
            parent = current;
            if (key > current.key) {
                current = current.right;
                isLeftChild = false;
            } else {
                current = current.left;
                isLeftChild = true;
            }
        }
        console.log(parent);
        if (current) {
            // 第一种情况 叶结点
            if (!current.left && !current.right) {
                if (current == this.root) {
                    this.root = null;
                    return true;
                }
                if (isLeftChild) {
                    parent.left = null;
                } else {
                    parent.right = null;
                }
                return true;
            }
            //第二种情况 left不为空
            else if (current.right === null) {
                if (parent) {
                    if (isLeftChild) {
                        parent.left = current.left;
                    } else {
                        parent.right = current.left;
                    }
                } else {
                    this.root = current.left;
                }
                return true;
            }
            //第三种情况 right不为空
            else if (current.left === null) {
                if (parent) {
                    if (isLeftChild) {
                        parent.left = current.right;
                    } else {
                        parent.right = current.right;
                    }
                } else {
                    this.root = current.right;
                }
                return true;
            }
            //第四种情况 left right 都有值
            else {
                var recent = current.left;
                if (!parent) {
                    let recentParent;
                    while (recent.right) {
                        recentParent = recent;
                        recent = recent.right;
                    }
                    recent.left = this.root.left;
                    recent.right = this.root.right;
                    this.root = recent;
                    recentParent.right = null;
                } else {
                    while (recent.right) {
                        recent = recent.right;
                    }
                    if (isLeftChild) {
                        parent.left = recent;
                        recent.right = current.right;
                    } else {
                        parent.right = recent;
                        recent.right = current.right;
                    }
                }

                return true;
            }
        }
        return false;
    }
}

var binarySearchTree = new LxBinarySearchTree();

binarySearchTree.insert(9);
binarySearchTree.insert(5);
binarySearchTree.insert(7);
binarySearchTree.insert(13);
binarySearchTree.insert(15);
binarySearchTree.insert(11);
binarySearchTree.insert(17);
binarySearchTree.insert(10);

console.log(binarySearchTree.getMax());
console.log(binarySearchTree.getMin());
console.log(binarySearchTree.search(9));
console.log(binarySearchTree.delete(9));
var str = "";
binarySearchTree.preOrderTraversal((key) => {
    str += key + " ";
});
console.log(str);
console.log(binarySearchTree);
